1. Field of the Invention
The present invention relates to an apparatus and a method for carrying out a fast discrete cosine transform (to be called DCT below) with same positions of input and output data, and also relates to a recording medium which is readable by a computer with a program loaded thereon. Particularly, the present invention relates to an apparatus and a method for carrying out a fast discrete cosine transform with same positions of input and output data, and also relates to a recording medium readable by a computer with a program loaded thereon, in which in the case where a one-dimensional or two-dimensional forward or inverse discrete cosine transform is used for converting or inverse-converting digital signals, the required arithmetic amount is effectively reduced, and the positions of the input and output data are same, thereby making an additional memory needless.
2. Description of the Prior Art
Conventionally, there have been fast arithmetic methods for realizing one-dimensional and two-dimensional forward and inverse DCT. That is, there is U.S. Pat. No. 5,831,881 entitled xe2x80x9cMethod and Circuit for Forward/Inverse Discrete Cosine Transformxe2x80x9d issued on Nov. 3, 1998 to Fiedrich et al. Further, there is U.S. Pat. No. 5,719,963 entitled xe2x80x9cTwo-Dimensional Discrete Cosine Transform Computing Circuitxe2x80x9d issued on Feb. 17, 1998 to Kazui et. al. Furthermore, there is U.S. Pat. No. 5,748,514 entitled xe2x80x9cForward and Inverse Discrete Cosine Transform Circuitsxe2x80x9d issued on May 5, 1998 to Okada et. al.
In the above cited methods, in order to carry out a fast discrete cosine transform, there are included: a procedure of transposing the sequence of the input data; a butterfly arithmetic procedure; a repeated addition arithmetic procedure; and a procedure of transposing the sequence of the output data.
Thus the conventional methods undergo many procedures, and therefore, the arithmetic amount is enormously increased.
Particularly, in the conventional methods, the positions of the input and output data are not same in the intermediate arithmetic procedure. Therefore, in using the one-dimensional and two-dimensional forward/inverse DCT, there has to be used an additional memory.
The present invention is intended to overcome the above described disadvantages of the conventional techniques.
Therefore it is an object of the present invention to provide an apparatus and a method for carrying out a fast discrete cosine transform (DCT) with same positions of input and output data, and a recording medium readable by a computer with a program loaded thereon, in which, in the intermediate arithmetic procedure of the of the one-dimensional or two-dimensional forward or inverse DCT, the positions of the input and output data are same so as to make an additional memory needless.
It is another object of the present invention to provide an apparatus and a method for carrying out a fast discrete cosine transform with same positions of input and output data, and a recording medium readable by a computer with a program loaded thereon, in which the required arithmetic amount is effectively reduced.
In achieving the above objects, a first apparatus for carrying out a fast DCT with same positions of input and output data according to the present invention includes: an input data sequence transposing means for transposing the sequence of an externally inputted input data by using a transposing matrix E; a butterfly arithmetic means for carrying out a butterfly arithmetic operation by using a Gtxe2x88x921Btxe2x88x921.Gtxe2x88x922Btxe2x88x922 . . . G0B0 matrix on a data obtained as a result of transposing the sequence of the input data by the input data sequence transposing means; and a repeated addition and regularization arithmetic means for carrying out a repeated addition and regularization arithmetic operation by using an FkQ0Q1 . . . Qtxe2x88x921 matrix on a data obtained as a result of the butterfly arithmetic operation by the butterfly arithmetic means.
In a second aspect of the present invention, a first method applied to an apparatus for carrying out a fast DCT with same positions of input and output data according to the present invention includes the steps of: a) transposing the sequence of an externally inputted input data by using a transposing matrix E; b) carrying out a butterfly arithmetic operation by using a Gtxe2x88x921Btxe2x88x922. Gtxe2x88x922Btxe2x88x922 . . . G0B0 matrix on a data obtained as a result of transposing the sequence of the input data at the step b); and c) carrying out a repeated addition and regularization arithmetic operation by using an FkQ0Q1 . . . Qtxe2x88x921 matrix on a data obtained as a result of the butterfly arithmetic operation at the step b).
In a third aspect of the present invention, a second apparatus for carrying out a fast DCT with same positions of input and output data according to the present invention includes: a repeated addition and regularization arithmetic means for carrying out a repeated addition and regularization arithmetic operation by using an Qtxe2x88x921TQtxe2x88x922T . . . Q0T.Fk matrix on an externally inputted data; a butterfly arithmetic means for carrying out a butterfly arithmetic operation by using a B0G0.B1G1 . . . Btxe2x88x921Gtxe2x88x921 matrix on a data obtained as a result of carrying out a repeated addition and regularization arithmetic operation by the repeated addition and regularization arithmetic means; and an input data sequence transposing means for transposing the sequence of an output data by using a transposing matrix ET on a data obtained by carrying out the butterfly arithmetic operation by the butterfly arithmetic means.
In a fourth aspect of the present invention, a second method applied to an apparatus for carrying out a fast DCT with same positions of input and output data according to the present invention includes the steps of: a) carrying out a repeated addition and regularization arithmetic operation by using an Qtxe2x88x921TQtxe2x88x922T . . . Q0T.Fk matrix on an externally inputted data; b) carrying out a butterfly arithmetic operation by using a B0G0.B1G1 . . . Btxe2x88x921Gtxe2x88x921 matrix on a data obtained as a result of carrying out a repeated addition and regularization arithmetic operation by the repeated addition and regularization arithmetic means at the step a); and c) transposing the sequence of the data by using a transposing matrix ET on a data obtained by carrying out the butterfly arithmetic operation at the step b).
In a fifth aspect of the present invention, a third apparatus for carrying out a fast DCT with same positions of input and output data according to the present invention includes: an input data row sequence/column sequence transposing means for transposing the sequences of rows and columns of an externally inputted two-dimensional input data by using transposing matrices ET and E; and a row/column DCT means for carrying out a one-dimensional forward DCT by using an Fkxc2x7{Q0xc2x7Q1xcex9Qtxe2x88x921}xc2x7{Gtxe2x88x921Btxe2x88x921xc2x7Gtxe2x88x922Btxe2x88x922xcex9G0B0} matrix on a row data obtained as a result of transposing the sequences of rows and columns of the externally inputted two-dimensional input data by the input data row sequence/column sequence transposing means, and for carrying out a one-dimensional forward DCT by using a {B0G0xc2x7B1G1xcex9Btxe2x88x921Gtxe2x88x921}xc2x7{Qtxe2x88x921Txc2x7Qtxe2x88x922xcex9Q0T}Fk matrix on a column data obtained as a result of transposing the sequences of rows and columns of the externally inputted two-dimensional input data by the input data row sequence/column sequence transposing means.
In a sixth aspect of the present invention, a third method applied to an apparatus for carrying out a fast DCT with same positions of input and output data according to the present invention includes the steps of: a) transposing the sequences of rows and columns of an externally inputted two-dimensional input data by using transposing matrices ET and E; and b) carrying out a one-dimensional forward DCT by using an Fk.{Q0.Q1xcex9Qtxe2x88x921}.{Gtxe2x88x921Btxe2x88x921.Gtxe2x88x922Btxe2x88x922xcex9G0B0} matrix on a row data obtained as a result of transposing the sequences of rows and columns of the externally inputted two-dimensional input data by the input data row sequence/column sequence transposing means at the step a), and c) carrying out a one-dimensional forward DCT by using a {B0G0.B1G1xcex9Btxe2x88x921Gtxe2x88x921}.{Qtxe2x88x921T.Qtxe2x88x922Txcex9Q0T}Fk matrix on a column data obtained as a result of transposing the sequences of rows and columns of the externally inputted two-dimensional input data by the input data row sequence/column sequence transposing means at the step a).
In 7th aspect of the present invention, a fourth apparatus for carrying out a fast DCT with same positions of input and output data according to the present invention includes: a row/column DCT means for carrying out a one-dimensional inverse DCT by using a {B0G0.B1G1xcex9Btxe2x88x921Gtxe2x88x921}.{txe2x88x921T.Qtxe2x88x922Txcex9Q0T}Fk matrix on a row data of an externally inputted two-dimensional input data, and for carrying out a one-dimensional inverse DCT by using an Fk.{Q0.Q1xcex9Qtxe2x88x921}.{Gtxe2x88x921Btxe2x88x921.Gtxe2x88x922Btxe2x88x922xcex9G0B0} matrix on a column data of the externally inputted two-dimensional input data; and an input data row sequence/column sequence transposing means for transposing the sequences of rows and columns of the two-dimensional input data obtained from the row/column inverse DCT means by using transposing matrices ET and E.
In an 8th aspect of the present invention, a fourth method applied to an apparatus for carrying out a fast DCT with same positions of input and output data according to the present invention includes the steps of: a) carrying out a one-dimensional inverse DCT by using a {B0G0.B1G1xcex9Btxe2x88x921Gtxe2x88x921}.{Qtxe2x88x921T.Qtxe2x88x922Txcex9Q0T}Fk matrix on a row data of an externally inputted two-dimensional input data, and for carrying out a one-dimensional inverse DCT by using an Fk.{Q0.Q1xcex9Qtxe2x88x921}.{Gtxe2x88x921Btxe2x88x921.Gtxe2x88x922Btxe2x88x922xcex9G0B0} matrix on a column data of the externally inputted two-dimensional input data; and b) transposing the sequences of rows and columns of the two-dimensional input data obtained from the row/column inverse DCT means by using transposing matrices ET and E.
In a 9th aspect of the present invention, a fifth apparatus for carrying out a fast DCT with same positions of input and output data according to the present invention includes: an input data row sequence/column sequence transposing means for transposing the sequences of rows and columns of an externally inputted two-dimensional input data by using a transposing matrix (ST{circle around (X)}ST)(EN{circle around (X)}EN); a butterfly arithmetic means for carrying out a butterfly arithmetic operation by using a
{(ST{circle around (X)}ST)(Atxe2x88x921{circle around (X)}Atxe2x88x921)(S{circle around (X)}S)}{ST{circle around (X)}ST}(Htxe2x88x921{circle around (X)}Htxe2x88x921)(S{circle around (X)}S)}
xcex9{(ST{circle around (X)}ST)(A0{circle around (X)}A0)(S{circle around (X)}S)}{(ST{circle around (X)}ST)(H0{circle around (X)}H0)(S{circle around (X)}S)}
matrix on a two-dimensional data obtained as a result of transposing the sequences of the two dimensional data by the input data row sequence/column sequence transposing means; and a repeated addition and regularization arithmetic means for carrying out a repeated addition and regularization arithmetic operation by using a (Fk{circle around (X)}Fk)(Q0{circle around (X)}IN)xcex9(Qtxe2x88x921{circle around (X)}IN)(IN{circle around (X)}Q0)xcex9(IN{circle around (X)}Qtxe2x88x921) matrix on a data obtained as a result of the butterfly arithmetic operation by the butterfly arithmetic means.
In a 10th aspect of the present invention, a 5th method applied to an apparatus for carrying out a fast DCT with same positions of input and output data according to the present invention includes the steps of: a) transposing the sequences of rows and columns of an externally inputted two-dimensional input data by using a transposing matrix (ST{circle around (X)}ST).(EN{circle around (X)}EN); b) carrying out a butterfly arithmetic operation by using a
{(ST{circle around (X)}ST)(Atxe2x88x921{circle around (X)}Atxe2x88x921)(S{circle around (X)}S)}{ST{circle around (X)}ST}(Htxe2x88x921{circle around (X)}Htxe2x88x921)(S{circle around (X)}S)}
xcex9{(ST{circle around (X)}ST)(A0{circle around (X)}A0)(S{circle around (X)}S)}{(ST{circle around (X)}ST)(H0{circle around (X)}H0)(S{circle around (X)}S)}
matrix on a two-dimensional data obtained as a result of transposing the sequences of the two dimensional data by the input data row sequence/column sequence transposing means at the step a); and c) carrying out a repeated addition and regularization arithmetic operation by using a (Fk{circle around (X)}Fk)(Q0{circle around (X)}IN)xcex9Qtxe2x88x921{circle around (X)}IN)(IN{circle around (X)}Q0)xcex9(IN{circle around (X)}Qtxe2x88x921) matrix on a data obtained as a result of the butterfly arithmetic operation by the butterfly arithmetic means at the step b).
In an 11th aspect of the present invention, a 6th apparatus for carrying out a fast DCT with same positions of input and output data according to the present invention includes: a repeated addition and regularization arithmetic means for carrying out a repeated addition and regularization arithmetic operation by using a (Qtxe2x88x921T{circle around (X)}IN)xcex9(Q0T{circle around (X)}IN)(IN{circle around (X)}Q0txe2x88x921T)xcex9(IN{circle around (X)}Q0T)(Fk{circle around (X)}Fk) matrix on an externally inputted two-dimensional input data; a butterfly arithmetic means for carrying out a butterfly arithmetic operation by using a
{(S{circle around (X)}S)(A0{circle around (X)}A0)(ST{circle around (X)}ST)}{(S{circle around (X)}S)(H0{circle around (X)}H0)(ST{circle around (X)}ST)}
xcex9{(S{circle around (X)}S)(Atxe2x88x921{circle around (X)}Atxe2x88x921)(ST{circle around (X)}ST)}{(S{circle around (X)}S)(Htxe2x88x921{circle around (X)}Hxe2x88x9210)(ST{circle around (X)}ST)
matrix on a two-dimensional data obtained as a result of carrying out the repeated addition and regularization arithmetic operation by the repeated addition and regularization arithmetic means; and an output data sequence transposing means for transposing the sequence of a two-dimensional output data by using a (ENT{circle around (X)}ENT)(S{circle around (X)}S) matrix on a two-dimensional data obtained as a result of carrying out the butterfly arithmetic operation by the butterfly arithmetic means.
In a 12th aspect of the present invention, a 6th method applied to an apparatus for carrying out a fast DCT with same positions of input and output data according to the present invention includes the steps of: a) carrying out a repeated addition and regularization arithmetic operation by using a (Qtxe2x88x921T{circle around (X)}IN)xcex9(Q0T{circle around (X)}IN)(IN{circle around (X)}Qtxe2x88x921T)xcex9(IN{circle around (X)}Q0T)(Fk{circle around (X)}Fk) matrix on an externally inputted two-dimensional input data; b) carrying out a butterfly arithmetic operation by using a
xe2x80x83{(S{circle around (X)}S)(A0{circle around (X)}A0)(ST{circle around (X)}ST)}{(S{circle around (X)}S)(H0{circle around (X)}H0)(ST{circle around (X)}ST)
xcex9{(S{circle around (X)}S)(Atxe2x88x921{circle around (X)}Atxe2x88x921)(ST{circle around (X)}ST)}{(S{circle around (X)}S)(Htxe2x88x921{circle around (X)}Htxe2x88x921)(ST{circle around (X)}ST)}
matrix on a two-dimensional data obtained as a result of carrying out the repeated addition and regularization arithmetic operation on the two dimensional data by the repeated addition and regularization arithmetic means at the step b); and c) transposing the sequence of a two-dimensional output data by using a (ENT{circle around (X)}ENT)(S{circle around (X)}S) matrix on a two-dimensional data obtained as a result of carrying out the butterfly arithmetic operation by the butterfly arithmetic means at the step b).
In a thirteenth aspect of the present invention, a recording medium readable by a computer and with a program loaded thereon to be applied to a fast DCT arithmetic apparatus according to the present invention includes: a first function of transposing the sequence of an externally inputted input data by using a transposing matrix E; a second function of carrying out a butterfly arithmetic operation by using a Gtxe2x88x921Btxe2x88x921.Gtxe2x88x922Btxe2x88x922 . . . G0B0 matrix on a data obtained as a result of transposing the sequence of the input data by the first function; and a third function of carrying out a repeated addition and regularization arithmetic operation by using an FkQ0Q1 . . . Qtxe2x88x921 matrix on a data obtained as a result of the butterfly arithmetic operation by the second function.
In a fourteenth aspect of the present invention, a recording medium readable by a computer, with a program loaded thereon to be applied to a fast DCT arithmetic apparatus according to the present invention includes: a first function of carrying out a repeated addition and regularization arithmetic operation by using a Qtxe2x88x921TQtxe2x88x922T . . . Q0T.Fk matrix on an externally inputted data; a second function of carrying out a butterfly arithmetic operation by using a B0G0.B1G1 . . . Btxe2x88x921Gtxe2x88x921 matrix on a data obtained as a result of carrying out a repeated addition and regularization arithmetic operation by the first function; and a third function of transposing the sequence of an output data by using a transposing matrix ET on a data obtained by transposing the sequence of the externally inputted input data by the second function.
In a 15th aspect of the present invention, a recording medium readable by a computer, with a program loaded thereon to be applied to a fast DCT arithmetic apparatus according to the present invention includes: a first function of transposing the sequences of rows and columns of an externally inputted two-dimensional input data by using transposing matrices ET and E; and a second function of carrying out a one-dimensional forward DCT by using an Fk.{Q0.Q1xcex9Qtxe2x88x921}.{Gtxe2x88x921Btxe2x88x921.Gtxe2x88x922Btxe2x88x922xcex9G0B0} matrix on a row data obtained as a result of transposing the sequences of rows and columns of the externally inputted two-dimensional input data by the first function, and carrying out a one-dimensional forward DCT by using a {B0G0.B1G1xcex9Btxe2x88x921Gtxe2x88x921}.{Qtxe2x88x921T.Qtxe2x88x922Txcex9Q0T}Fk matrix on a column data obtained as a result of transposing the sequences of rows and columns of the externally inputted two-dimensional input data by the first function.
In a 16th aspect of the present invention, a recording medium readable by a computer, with a program loaded thereon to be applied to a fast DCT arithmetic apparatus according to the present invention includes: a first function of carrying out a one-dimensional inverse DCT by using a {B0G0.B1G1xcex9Btxe2x88x921Gtxe2x88x921}.{Qtxe2x88x921T.Qtxe2x88x922Txcex9Q0T}Fk matrix on a row data of an externally inputted two-dimensional input data, and carrying out a one-dimensional inverse DCT by using an Fk.{Q0.Q1xcex9Qtxe2x88x921}.{Gtxe2x88x921Btxe2x88x921.Gtxe2x88x922Btxe2x88x922xcex9G0B0} matrix on a column data of the externally inputted two-dimensional input data; and a second function of transposing the sequences of rows and columns of the two-dimensional input data obtained from the first function by using transposing matrices ET and E.
In a 17th aspect of the present invention, a recording medium readable by a computer, with a program loaded thereon to be applied to a fast DCT arithmetic apparatus according to the present invention includes: a first function of transposing the sequences of rows and columns of an externally inputted two-dimensional input data by using a transposing matrix (ST{circle around (X)}ST)(EN{circle around (X)}EN); a second function of carrying out a butterfly arithmetic operation by using a
{(ST{circle around (X)}ST)(Atxe2x88x921{circle around (X)}Atxe2x88x921)(S{circle around (X)}S)}{ST{circle around (X)}ST}(Htxe2x88x921{circle around (X)}Htxe2x88x921)(S{circle around (X)}S)}
xcex9{(ST{circle around (X)}ST)(A0{circle around (X)}A0)(S{circle around (X)}S)}{(ST{circle around (X)}ST)(H0{circle around (X)}H0)(S{circle around (X)}S)}
matrix on a two-dimensional data obtained as a result of transposing the sequences of the two dimensional data by the first function; and a third function of carrying out a repeated addition and regularization arithmetic operation by using a (Fk{circle around (X)}Fk)(Q0{circle around (X)}IN)xcex9(Qtxe2x88x921{circle around (X)}IN)(IN{circle around (X)}Q0)xcex9(IN{circle around (X)}Qtxe2x88x921) matrix on a data obtained as a result of the butterfly arithmetic operation by the butterfly arithmetic means.
In an 18th aspect of the present invention, a recording medium readable by a computer, with a program loaded thereon to be applied to a fast DCT arithmetic apparatus according to the present invention includes: a first function of carrying out a repeated addition and regularization arithmetic operation by using a (Qtxe2x88x921T{circle around (X)}IN)xcex9(Q0T{circle around (X)}IN)(IN{circle around (X)}Qtxe2x88x921T)xcex9(IN{circle around (X)}Q0T)(Fk{circle around (X)}Fk) matrix on an externally inputted two-dimensional input data; carrying out a butterfly arithmetic operation by using a
{(S{circle around (X)}S)(A0{circle around (X)}A0)(ST{circle around (X)}ST)}{(S{circle around (X)}S)(H0{circle around (X)}H0)(ST{circle around (X)}ST)}
xcex9{(S{circle around (X)}S)(Atxe2x88x921{circle around (X)}Atxe2x88x921)(ST{circle around (X)}ST)}{(S{circle around (X)}S)(Htxe2x88x921{circle around (X)}Htxe2x88x921)(ST{circle around (X)}ST)}
matrix on a two-dimensional data obtained as a result of carrying out the repeated addition and regularization arithmetic operation on the two dimensional data by the repeated addition and regularization arithmetic means; and transposing the sequence of a two-dimensional output data by using a (ENT{circle around (X)}ENT)(S{circle around (X)}S) matrix on a two-dimensional data obtained as a result of carrying out the butterfly arithmetic operation by the second function.